/*
leetcode 3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。


示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 

提示：

0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成
 */
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        unordered_map<char, int> map; // 哈希表记录字符的最新索引，map 的键是字符，值是该字符的最后出现的索引位置
        int max_len = 0; // 最长子串长度
        int left = 0; // 滑动窗口的左边界

        for (int right = 0; right < s.size(); ++right) {

            // 如果当前字符在窗口内出现过，更新窗口的左边界
            //如果 map.find(s[right]) 返回的不是 map.end()，意味着哈希表中存在字符 s[right]，
            //也就是说，字符 s[right] 在哈希表中出现过。
            
            //如果返回 map.end()，则说明哈希表中没有这个字符，即字符 s[right] 没有在哈希表中出现过。
            //map[s[right]] >= left，字符 s[right] 在窗口中的 上一次出现的位置 
            //大于等于当前窗口的左边界 left，那么就说明它是重复的。
            if (map.find(s[right]) != map.end() && map[s[right]] >= left) {
                //将 left 更新为字符 s[right] 最新出现位置的下一个位置
                left = map[s[right]] + 1;
            }
            
            // 更新当前字符的最新位置
            map[s[right]] = right;
            
            // 计算当前窗口的大小，更新最大长度
            max_len = max(max_len, right - left + 1);
        }

        return max_len;
    }
};

int main() {
    Solution sol;
    string s = "abcabcbb";
    cout << "The length of the longest substring without repeating characters is: " 
         << sol.lengthOfLongestSubstring(s) << endl;
    return 0;
}

/*
 遍历字符串 s，right 从 0 到 7：
1. right = 0，字符 'a'：
map.find(s[right]) != map.end() 检查字符 'a' 是否已经出现过。由于 map 为空，所以字符 'a' 不在其中。
更新哈希表：map['a'] = 0。字符 'a' 的最新索引是 0。
计算当前窗口大小：right - left + 1 = 0 - 0 + 1 = 1。
更新 max_len：max_len = max(0, 1) = 1。

2. right = 1，字符 'b'：
map.find(s[right]) != map.end() 检查字符 'b' 是否已经出现过。字符 'b' 不在哈希表中。
更新哈希表：map['b'] = 1。字符 'b' 的最新索引是 1。
计算当前窗口大小：right - left + 1 = 1 - 0 + 1 = 2。
更新 max_len：max_len = max(1, 2) = 2。

3. right = 2，字符 'c'：
map.find(s[right]) != map.end() 检查字符 'c' 是否已经出现过。字符 'c' 不在哈希表中。
更新哈希表：map['c'] = 2。字符 'c' 的最新索引是 2。
计算当前窗口大小：right - left + 1 = 2 - 0 + 1 = 3。
更新 max_len：max_len = max(2, 3) = 3。

4. right = 3，字符 'a'：
map.find(s[right]) != map.end() 检查字符 'a' 是否已经出现过。字符 'a' 已经在 map 中，且它的索引是 0（小于 right = 3）。
由于 'a' 重复了，我们需要更新滑动窗口的左边界：
left = map['a'] + 1 = 0 + 1 = 1，新的左边界是 1，即跳过 a 在左边的位置。
更新哈希表：map['a'] = 3。字符 'a' 的最新索引是 3。
计算当前窗口大小：right - left + 1 = 3 - 1 + 1 = 3。
max_len 仍然是 3（不更新）。

5. right = 4，字符 'b'：
map.find(s[right]) != map.end() 检查字符 'b' 是否已经出现过。字符 'b' 已经在 map 中，且它的索引是 1（小于 right = 4）。
由于 'b' 重复了，我们需要更新滑动窗口的左边界：
left = map['b'] + 1 = 1 + 1 = 2，新的左边界是 2，即跳过 b 在左边的位置。
更新哈希表：map['b'] = 4。字符 'b' 的最新索引是 4。
计算当前窗口大小：right - left + 1 = 4 - 2 + 1 = 3。
max_len 仍然是 3（不更新）。

6. right = 5，字符 'c'：
map.find(s[right]) != map.end() 检查字符 'c' 是否已经出现过。字符 'c' 已经在 map 中，且它的索引是 2（小于 right = 5）。
由于 'c' 重复了，我们需要更新滑动窗口的左边界：
left = map['c'] + 1 = 2 + 1 = 3，新的左边界是 3，即跳过 c 在左边的位置。
更新哈希表：map['c'] = 5。字符 'c' 的最新索引是 5。
计算当前窗口大小：right - left + 1 = 5 - 3 + 1 = 3。
max_len 仍然是 3（不更新）。

7. right = 6，字符 'b'：
map.find(s[right]) != map.end() 检查字符 'b' 是否已经出现过。字符 'b' 已经在 map 中，且它的索引是 4（小于 right = 6）。
由于 'b' 重复了，我们需要更新滑动窗口的左边界：
left = map['b'] + 1 = 4 + 1 = 5，新的左边界是 5，即跳过 b 在左边的位置。
更新哈希表：map['b'] = 6。字符 'b' 的最新索引是 6。
计算当前窗口大小：right - left + 1 = 6 - 5 + 1 = 2。
max_len 仍然是 3（不更新）。

8. right = 7，字符 'b'：
map.find(s[right]) != map.end() 检查字符 'b' 是否已经出现过。字符 'b' 已经在 map 中，且它的索引是 6（小于 right = 7）。
由于 'b' 重复了，我们需要更新滑动窗口的左边界：
left = map['b'] + 1 = 6 + 1 = 7，新的左边界是 7，即跳过 b 在左边的位置。
更新哈希表：map['b'] = 7。字符 'b' 的最新索引是 7。
计算当前窗口大小：right - left + 1 = 7 - 7 + 1 = 1。
max_len 仍然是 3（不更新）。
*/